// 创建节点
class Node {
  constructor (key) {
    this.key = key
    this.left = null
    this.right = null // 右节点
  }
}
// 二叉树:左子树系节点值 <根节点 右子树节点值 大于跟界节点
/// 封装二叉搜索树
class binarySearchTree {
  constructor () {
    this.root = null // 根节点
  }
  // 插入数据
  insert (key) {
    // 1.创建节点累
    let newNode = new Node(key)
    //如果根节点为空
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  insertNode (root, node) {
    if (node.key < root.key) {
      // 说明在左子树上
      if (root.left === null) {
        root.left = node
      } else {
        this.insertNode(root.left, node)
      }
    } else {
      if (root.right === null) {
        root.right = node
      } else {
        this.insertNode(root.right, node)
      }
    }
  }
  //先序遍历
  preorderTraversal () {
    let result = []
    this.preorderTraversalNode(this.root, result)
    return result
  }
  preorderTraversalNode (node, result) {
    if (node === null) return
    result.push(node.key)
    this.preorderTraversalNode(node.left, result)
    this.preorderTraversalNode(node.right, result)
  }
  // 中序遍历 先遍历左节点树 再根节点 再又右节点数
  inorderTraversal () {
    let result = []
    this.inorderTraversalNode(this.root, result)
    return result
  }
  inorderTraversalNode (node, result) {
    if (node === null) return
    this.inorderTraversalNode(node.left, result)
    result.push(node.key)
    this.inorderTraversalNode(node.right, result)
  }
  // 后序遍历 左右根
  postorderTraversal () {
    let result = []
    this.postorderTraversalNode(this.root, result)
    return result
  }
  postorderTraversalNode (node, result) {
    if (node === null) return
    this.postorderTraversalNode(node.left, result)
    this.postorderTraversalNode(node.right, result)
    result.push(node.key)
  }
  // 查找二叉搜索树的最小最大值
  min () {
    if (this.root === null) return null
    let node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }
  max () {
    if (this.root === null) return null
    let node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }
}
module.exports = {
  Node,
  binarySearchTree
};
// insert() 插入
// const BinarySearchTree = new binarySearchTree();
// BinarySearchTree.insert(11);
// BinarySearchTree.insert(7);
// BinarySearchTree.insert(5);
// BinarySearchTree.insert(3);
// BinarySearchTree.insert(9);
// BinarySearchTree.insert(8);
// BinarySearchTree.insert(10);
// BinarySearchTree.insert(15);
// BinarySearchTree.insert(13);
// BinarySearchTree.insert(12);
// BinarySearchTree.insert(14);
// BinarySearchTree.insert(20);
// BinarySearchTree.insert(18);
// BinarySearchTree.insert(25);
// BinarySearchTree.insert(19);
// console.log(BinarySearchTree);
// console.log(JSON.stringify(BinarySearchTree));
// console.log(BinarySearchTree.preorderTraversal());
// 在二叉搜索树中查找最值,最小值在二叉树的最左边 最大值在二叉搜索树的最右边
console.log(BinarySearchTree.min());
console.log(BinarySearchTree.max());